package com.atguigu.linkedlist;

import java.util.Stack;

/**
 * 单链表的实现(不考虑id的顺序)
 * @author WangJX
 * @version 1.0
 * @date 2019/9/17 23:32
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");

        HeroNode heroNode4 = new HeroNode(4, "公孙胜", "入云龙");
        HeroNode heroNode5 = new HeroNode(5, "关胜", "大刀");
        HeroNode heroNode6 = new HeroNode(6, "林冲", "豹子头");

        SingleLinkedList list1 = null;
        SingleLinkedList list2 = null;
        //添加数据
        try {
            list1 = new SingleLinkedList();
            list2 = new SingleLinkedList();


            list1.addById(heroNode3);
            list1.addById(heroNode1);
            list1.addById(heroNode5);

            list2.addById(heroNode4);
//            list2.addById(heroNode6);
//            list2.addById(heroNode2);

//            list1.add(heroNode3);
//            list1.add(heroNode1);
//            list1.add(heroNode2);


        } catch (Exception e) {
            e.printStackTrace();
        }

        //遍历数据
        System.out.println("第一个单链表：");
        list1.list();
        System.out.println("第二个单链表：");
        list2.list();


        //删除数据
//        list.delete(3);
//        list.delete(1);
//        list.delete(2);



        //修改单链表
//        HeroNode heroNode = new HeroNode(2, "小吴", "诸葛亮");
//        list.updata(heroNode);
//        System.out.println();

        //获得单链表有效节点个数
//        int length = SingleLinkedList.getLength(list.getHead());

//        int length = list.getLength(list.getHead());
//        System.out.println(length);

        //查找倒数第n个节点
//        HeroNode heroNode = SingleLinkedList.returnIndex(list.getHead(), 4);
//        System.out.println("要查找的倒数节点是：" + heroNode);

        //将单链表反转
//        SingleLinkedList.reversetList(list.getHead());
//        list.list();

        //将单链表反向输出
//        System.out.println("单链表反向输出：");
//        SingleLinkedList.reverseOutList(list.getHead());

        System.out.println("合并两个链表：");
        HeroNode heroNode = SingleLinkedList.joinList(list1.getHead(), list2.getHead());
        SingleLinkedList.list(heroNode);
    }
}

class SingleLinkedList {

    //先初始化一个头结点
    private HeroNode head = new HeroNode(0, "", "");

    /**
     * 添加单链表数据
     * @param heroNode
     */
    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        //遍历链表，找到最后一位数据
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //把数据指向下一位
        temp.next = heroNode;
    }

    /**
     * 根据id，顺序插入数据
     * @param heroNode
     */
    public void addById(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false;

        while (true) {
            //当数据遍历到最后一位还不满足，就添加到最后
            if (temp.next == null) {
                break;
            }
            //当temp后一位的id大于要插入的id，说明已经找到了要插入的位置
            if (temp.next.id > heroNode.id) {
                break;
            } else if (temp.next.id == heroNode.id) {   //当要插入的id等于找到位置后一位的id，说明id重复
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //判断id是否重复，重复给出提示，不重复插入数据
        if (flag) {
            throw new RuntimeException("要添加的id重复：" + heroNode.id);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    /**
     * 修改单链表指定id节点信息
     * @param newheroNode   要修改的数据
     */
    public void updata(HeroNode newheroNode) {
        if (head.next == null) {
            throw new RuntimeException("链表为空!");
        }
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            //如果下一个节点信息为null，代表已经到了链表的最后
            if (temp.next == null) {
                break;
            }
            //如果temp的id和要修改的id相等，说明找到了要修改的节点
            if (temp.next.id == newheroNode.id) {
                flag = true;
                break;
            }

            temp = temp.next;
        }
        //如果flag为true，说明找了要修改的节点
        if (flag) {
            temp.next.name = newheroNode.name;
            temp.next.nickname = newheroNode.nickname;
        } else {
            throw new RuntimeException("没有该id的节点");
        }

    }

    /**
     * 删除单链表指定id节点
     * @param id    要删除的id
     */
    public void delete(int id) {
        if (head.next == null) {
            throw new RuntimeException("链表为空!");
        }

        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.id == id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            throw new RuntimeException("没有要删除的id!");
        }
    }


    /**
     * 获得单链表节点有效节点个数
     * @param headNode  传入一个头节点
     * @return  返回列表节点个数
     */
    public static int getLength(HeroNode headNode) {
        if (headNode.next == null) {
            throw new RuntimeException("链表为空");
        }
        HeroNode temp = headNode;

        int count = 0;
        while (temp.next != null) {
            count++;
            temp = temp.next;
        }

        return count;
    }

    /**
     * 查询指定倒数位数内容
     * @param headNode  头节点
     * @param num   指定位数
     * @return  查找的内容
     */
    public static HeroNode returnIndex(HeroNode headNode, int num) {
        if (headNode.next == null) {
            throw new RuntimeException("列表为空");
        }

        HeroNode temp = headNode.next;
        int length = SingleLinkedList.getLength(headNode);
        if (num < 0 || num > length){
            throw new RuntimeException("输入的数字超范围");
        }
        for (int i = 0; i < length - num; i++) {
            temp = temp.next;
        }

        return temp;
    }

    /**
     * 单链表反转
     * @param headNode  传入列表头
     */
    public static void reversetList(HeroNode headNode) {
        if (headNode.next == null) {
            throw new RuntimeException("链表为空");
        }
        if (headNode.next.next == null) {
            return;
        }

        HeroNode demp = headNode.next;
        HeroNode next = null;   //指定当前节点的下一个节点
        HeroNode reverseHead = new HeroNode(0, "", ""); //指定第二个链表
        //遍历原来的链表，每遍历一个节点，就取出一个节点插入到第二个链表
        while (demp != null) {
            next = demp.next;
            demp.next = reverseHead.next;
            reverseHead.next = demp;
            demp = next;
        }
        //把反转后的链表给链表头
        headNode.next = reverseHead.next;
    }

    /**
     * 单链表反向打印(使用stack栈)
     * @param headNode
     */
    public static void reverseOutList(HeroNode headNode) {
        if (headNode.next == null) {
            throw new RuntimeException("链表为空");
        }
        HeroNode cur = headNode.next;

        //把数据放入栈中
        Stack<HeroNode> nodes = new Stack<>();
        while (cur != null) {
            nodes.push(cur);
            cur = cur.next;
        }

        //打印输出
        while (nodes.size() > 0) {
            System.out.println(nodes.pop());
        }
    }



    /**
     * 合并两个有序单链表，合并后的链表依然有序
     * @param one   第一个有序链表头
     * @param two   第二个有序链表头
     */
    public static HeroNode joinList(HeroNode one, HeroNode two) {
        if (one.next == null && two.next == null) {
            throw new RuntimeException("传入的链表都为空");
        } else if (one.next == null && two.next != null) {
            return two;
        }else if (one.next != null && two.next == null) {
            return one;
        }

        HeroNode head = new HeroNode(0, "", "");
        HeroNode heroNode = head;
        HeroNode cur = one.next;
        HeroNode temp = two.next;
        while (cur != null || temp!= null) {

            if (cur == null) {
                while (temp != null) {
                    heroNode.next = temp;
                    heroNode = heroNode.next;
                    temp = temp.next;
                }
                break;
            } else if (temp == null) {
                while (cur != null) {
                    heroNode.next = cur;
                    heroNode = heroNode.next;
                    cur = cur.next;
                }
                break;
            }

            if (cur.id < temp.id) {
                heroNode.next = cur;
                heroNode = heroNode.next;
                cur = cur.next;
            } else {
                heroNode.next = temp;
                heroNode = heroNode.next;
                temp = temp.next;
            }
        }

        return head;
    }


    public static void list(HeroNode headNode) {
        if (headNode.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = headNode.next;
        while (true) {
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


    /**
     * 遍历单链表
     */
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = head.next;
        while (true) {
            if (temp == null){
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }

    public HeroNode getHead() {
        return head;
    }
}

//链表存储的数据类型
class HeroNode {
    public int id;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "id=" + id +
                ", name=" + name +
                ", nickname=" + nickname ;
    }
}


